package cn.hughie.queue;

import utils.SortUtils;

import java.util.Random;

/**
 * 最小索引堆
 *
 * @author yuh
 * @date 2018/5/16 18:07
 */
public class IndexMinPq<E extends Comparable<E>> {

    /**
     * 容量
     */
    private int maxCapacity;

    /**
     * 队列内的元素
     */
    private E[] eles;

    /**
     * 索引堆
     */
    private int[] index;

    /**
     * 反向索引堆
     */
    private int[] reverse;

    /**
     * 元素个数
     */
    private int n;

    public IndexMinPq(int maxIndex) {
        this.maxCapacity = maxIndex;
        index = new int[maxIndex + 1];
        reverse = new int[maxIndex + 1];
        eles = (E[]) new Comparable[maxIndex + 1];
        for (int i = 0; i < reverse.length; i++) {
            reverse[i] = -1;
        }
    }

    /**
     * 是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return n == 0;
    }


    /**
     * 插入一个元素
     *
     * @param k
     * @param e
     */
    public void insert(int k, E e) {
        eles[k] = e;
        index[++n] = k;
        reverse[k] = n;
        swim(n);
    }

    /**
     * 查看最上面的元素
     *
     * @return
     */
    public E peekEle() {
        return eles[index[1]];
    }

    /**
     * 获取最上面的索引
     *
     * @return
     */
    public int peekIndex() {
        return index[1];
    }

    public E popEle() {
        E minEle = eles[index[1]];
        exch(1, n--);
        eles[index[n + 1]] = null;
        reverse[index[n + 1]] = -1;
        sink(1);
        return minEle;
    }

    public void change(int k, E ele) {
        eles[k] = ele;
        swim(reverse[k]);
        sink(reverse[k]);
    }

    /**
     * 交换元素
     *
     * @param i
     * @param j
     */
    private void exch(int i, int j) {
        int tmp = index[i];
        index[i] = index[j];
        index[j] = tmp;

        reverse[index[i]] = i;
        reverse[index[j]] = j;
    }

    /**
     * 上浮操作
     *
     * @param k 这是index的角标
     */
    private void swim(int k) {
        while (k > 1 && SortUtils.largerThan(eles[index[k / 2]], eles[index[k]])) {
            exch(k, k / 2);
            k /= 2;
        }
    }

    /**
     * 下沉操作
     *
     * @param k 这是index的角标
     */
    private void sink(int k) {
        while (2 * k <= n) {
            int c = 2 * k;
            if (c + 1 <= n && SortUtils.largerThan(eles[index[c]], eles[index[c + 1]])) {
                c++;
            }
            if (!SortUtils.largerThan(eles[index[k]], eles[index[c]])) {
                break;
            }
            exch(k, c);
            sink(c);
        }

    }

    public static void main(String[] args) {
        IndexMinPq<Integer> minPq = new IndexMinPq<>(10);
        Random random = new Random(10000L);
        for (int i = 0; i < 10; i++) {
            minPq.insert(i, random.nextInt(1000));
        }
        System.out.println();
        while (!minPq.isEmpty()){
            System.out.println(minPq.popEle());
        }
    }


}
